package com.buddy.learn.algorithm.simple;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Buddy
 * @date 2021/5/25
 */
public class _复原IP地址 {
    static final int SEG_COUNT = 4;
    static List<String> list = new ArrayList<String>();
    static int[] segments = new int[SEG_COUNT];

    public static void main(String[] args) {
//        String s = "25525511135";
        String s = "0000";
        System.out.println(JSON.toJSONString(restoreIpAddress(s)));
    }

    private static List<String> restoreIpAddress(String s) {
        segments = new int[SEG_COUNT];
        dfs(s, 0, 0);
        return list;
    }

    /**
     * 我们正在从 segStart 的位置开始，搜索 IP 地址中的第  segId 段
     * 其中 segId∈{0,1,2,3}。
     * 由于 IP 地址的每一段必须是 [0, 255] 中的整数，
     * 因此我们从  segStart 开始，从小到大依次枚举当前这一段 IP 地址的结束位置 segEnd。
     * 如果满足要求，就递归地进行下一段搜索，调用递归函数  dfs(segId+1,segEnd+1)。
     *
     * @param s        字符串
     * @param segId    第几段，一共四段
     * @param strStart 字符串的位置
     */
    private static void dfs(String s, int segId, int strStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案

        if (segId == SEG_COUNT) {
            if (strStart == s.length()) {
                StringBuffer sb = new StringBuffer();
                for (int i = 0; i < SEG_COUNT; i++) {
                    sb.append(segments[i]);
                    if (i != SEG_COUNT - 1) {
                        sb.append(".");
                    }

                }
                list.add(sb.toString());
            }
            return;
        }
        // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
        if (strStart == s.length()) {
            return;
        }

        // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
        if (s.charAt(strStart) == '0') {
            segments[segId] = 0;
            dfs(s, segId + 1, strStart + 1);
        }

        // 一般情况，枚举每一种可能性并递归
        int addr = 0;
        for (int i = strStart; i < s.length(); i++) {
            addr = addr * 10 + s.charAt(i) - '0';
            if (addr > 0 && addr <= 255) {
                segments[segId] = addr;
                dfs(s, segId + 1, i + 1);
            } else {
                break;
            }
        }

    }
}
